{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Operations to Form Subsequence With Target Sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #bit-manipulation #array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #位运算 #数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minOperations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #使子序列的和等于目标的最少操作次数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong>&nbsp;开始的数组&nbsp;<code>nums</code>&nbsp;，它包含 <strong>非负</strong>&nbsp;整数，且全部为 <code>2</code>&nbsp;的幂，同时给你一个整数&nbsp;<code>target</code>&nbsp;。</p>\n",
    "\n",
    "<p>一次操作中，你必须对数组做以下修改：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>选择数组中一个元素&nbsp;<code>nums[i]</code>&nbsp;，满足&nbsp;<code>nums[i] &gt; 1</code>&nbsp;。</li>\n",
    "\t<li>将&nbsp;<code>nums[i]</code>&nbsp;从数组中删除。</li>\n",
    "\t<li>在 <code>nums</code>&nbsp;的 <strong>末尾</strong>&nbsp;添加 <strong>两个</strong>&nbsp;数，值都为&nbsp;<code>nums[i] / 2</code>&nbsp;。</li>\n",
    "</ul>\n",
    "\n",
    "<p>你的目标是让 <code>nums</code>&nbsp;的一个 <strong>子序列</strong>&nbsp;的元素和等于&nbsp;<code>target</code>&nbsp;，请你返回达成这一目标的 <strong>最少操作次数</strong>&nbsp;。如果无法得到这样的子序列，请你返回 <code>-1</code>&nbsp;。</p>\n",
    "\n",
    "<p>数组中一个 <strong>子序列</strong>&nbsp;是通过删除原数组中一些元素，并且不改变剩余元素顺序得到的剩余数组。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [1,2,8], target = 7\n",
    "<b>输出：</b>1\n",
    "<b>解释：</b>第一次操作中，我们选择元素 nums[2] 。数组变为 nums = [1,2,4,4] 。\n",
    "这时候，nums 包含子序列 [1,2,4] ，和为 7 。\n",
    "无法通过更少的操作得到和为 7 的子序列。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [1,32,1,2], target = 12\n",
    "<b>输出：</b>2\n",
    "<b>解释：</b>第一次操作中，我们选择元素 nums[1] 。数组变为 nums = [1,1,2,16,16] 。\n",
    "第二次操作中，我们选择元素 nums[3] 。数组变为 nums = [1,1,2,16,8,8] 。\n",
    "这时候，nums 包含子序列 [1,1,2,8] ，和为 12 。\n",
    "无法通过更少的操作得到和为 12 的子序列。</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [1,32,1], target = 35\n",
    "<b>输出：</b>-1\n",
    "<b>解释：</b>无法得到和为 35 的子序列。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 1000</code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 2<sup>30</sup></code></li>\n",
    "\t<li><code>nums</code>&nbsp;只包含非负整数，且均为 2 的幂。</li>\n",
    "\t<li><code>1 &lt;= target &lt; 2<sup>31</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-operations-to-form-subsequence-with-target-sum](https://leetcode.cn/problems/minimum-operations-to-form-subsequence-with-target-sum/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-operations-to-form-subsequence-with-target-sum](https://leetcode.cn/problems/minimum-operations-to-form-subsequence-with-target-sum/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,8]\\n7', '[1,32,1,2]\\n12', '[1,32,1]\\n35']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        nums.sort(reverse = True)\n",
    "        t=0\n",
    "        while nums[0]!=0:\n",
    "            for i in range(len(nums)):\n",
    "                if nums[i]%2!=0:\n",
    "                    nums[i]-=1\n",
    "                    t+=1\n",
    "            for i in range(len(nums)):\n",
    "                nums[i]=nums[i]//2\n",
    "            t+=1\n",
    "        return t-1 if t!=0 else 0\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        for i in range(31):\n",
    "            Flag = 0\n",
    "            for j in range(n):\n",
    "                ans += nums[j] & 1\n",
    "                nums[j] >>= 1\n",
    "                Flag += nums[j]\n",
    "            ans += 1\n",
    "            if Flag == 0:\n",
    "                return ans - 1\n",
    "        return ans - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        res = 0\n",
    "        while True:\n",
    "            for i in range(n):\n",
    "                if nums[i] % 2 == 1:\n",
    "                    res += 1\n",
    "                nums[i] >>= 1\n",
    "            if sum(nums) == 0:\n",
    "                break\n",
    "            res += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        while True:\n",
    "            if not any(x > 0 for x in nums):\n",
    "                break\n",
    "\n",
    "            for i in range(len(nums)):\n",
    "                if nums[i] % 2:\n",
    "                    res += 1\n",
    "                    nums[i] -= 1\n",
    "\n",
    "            if not any(x > 0 for x in nums):\n",
    "                break\n",
    "\n",
    "            for i in range(len(nums)):\n",
    "                nums[i] //= 2\n",
    "\n",
    "            res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums); cnt = 0\n",
    "        while (1):\n",
    "            for i in range(n):\n",
    "                if nums[i] & 1: cnt += 1\n",
    "                nums[i] >>= 1\n",
    "            if sum(nums) == 0: break\n",
    "            cnt += 1\n",
    "        return cnt\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def help(self, nums):\n",
    "        even = True\n",
    "        step = 0\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] % 2 != 0:\n",
    "                even = False\n",
    "                nums[i] -= 1\n",
    "                step += 1\n",
    "        if even:\n",
    "            for i in range(len(nums)):\n",
    "                nums[i] = nums[i] // 2\n",
    "            step = 1\n",
    "        return nums, step\n",
    "\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        # 逆向思考如何将nums全部变为0\n",
    "        # 允许两种操作 一种是直接减半 第二种是某个数-1\n",
    "        # 每一步判断如果全是偶数 选择除以2\n",
    "        # 如果存在奇数 该奇数建议变成偶数\n",
    "\n",
    "        # 2 4 5\n",
    "        # 2 4 4\n",
    "        # 1 2 2\n",
    "        # 0 2 2\n",
    "        # 0 1 1\n",
    "        # 0 0 1\n",
    "        # 0 0 0\n",
    "\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        while nums.count(0) != n:\n",
    "            nums, step = self.help(nums)\n",
    "            ans += step\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        b=big=0\n",
    "        h=0\n",
    "        for i in nums:\n",
    "            if i>b:\n",
    "                b=i\n",
    "            h+=i.bit_count()\n",
    "        if b==0:return 0\n",
    "        c =-1\n",
    "        while b:\n",
    "            b>>=1\n",
    "            c+=1 \n",
    "        return c+ h\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        la=[0] *31\n",
    "        for n in nums:\n",
    "            for i in range(31):\n",
    "                la[i]+= 1&(n>>i)\n",
    "\n",
    "        #倒序，是关键\n",
    "        j=30 \n",
    "        while j>-1 and la[j]==0:\n",
    "            j-=1\n",
    "        if j<0:return 0\n",
    "        return sum(la)+j"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        la=[0] *31\n",
    "        for n in nums:\n",
    "            i=0\n",
    "            while n:\n",
    "                n,yu =divmod(n,2)\n",
    "                la[i]+=yu \n",
    "                i+=1\n",
    "        he =la[0]\n",
    "        f=0\n",
    "        #倒序，是关键\n",
    "        for j in range(30,0,-1):\n",
    "            if f==0 and la[j]>0:\n",
    "                f=1\n",
    "            if f:\n",
    "                he+=la[j]+1\n",
    "        return he"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "      maxVal = 0\n",
    "      cnt = 0\n",
    "      for num in nums:\n",
    "        maxVal = max(num, maxVal)\n",
    "        cnt += num.bit_count()\n",
    "      maxVal >>= 1\n",
    "      while maxVal:\n",
    "        cnt += 1\n",
    "        maxVal >>= 1\n",
    "      return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        plus_count = 0\n",
    "        max_multi_count = 0\n",
    "        for i in nums:\n",
    "            binval = bin(i)\n",
    "            length = len(binval) - 2\n",
    "            plus_count += binval.count(\"1\")\n",
    "            if length > 1:\n",
    "                multi_count = length - 1\n",
    "                max_multi_count = max(multi_count, max_multi_count)\n",
    "        return plus_count + max_multi_count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums) -> int:\n",
    "        plus_count = 0\n",
    "        max_multi_count = 0\n",
    "        for num in nums:\n",
    "            if num == 0:\n",
    "                continue\n",
    "            val = num\n",
    "            count = 0\n",
    "            while val > 1:\n",
    "                remain = val % 2\n",
    "                val = val >> 1\n",
    "                count += 1\n",
    "                if remain > 0:\n",
    "                    plus_count += 1\n",
    "            if num != 0:\n",
    "                plus_count += 1\n",
    "            max_multi_count = max(max_multi_count, count)\n",
    "        return plus_count + max_multi_count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        ans=0\n",
    "        for v in nums:\n",
    "            ans+=v.bit_count()\n",
    "        a=max(nums)\n",
    "        if a==0: return 0\n",
    "        while a:\n",
    "            a=a>>1\n",
    "            ans+=1\n",
    "        return ans-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        op_2_min = 0  # 第2种操作的最小次数\n",
    "        op_1 = 0  # 第1种操作的次数总数\n",
    "        for num in nums:\n",
    "            op_2 = 0\n",
    "            while num:\n",
    "                if num % 2 == 1:\n",
    "                    num -= 1\n",
    "                    op_1 += 1\n",
    "                else:\n",
    "                    num //= 2\n",
    "                    op_2 += 1\n",
    "            op_2_min = max(op_2_min, op_2)\n",
    "\n",
    "        return op_1 + op_2_min\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        max_num = max(nums)\n",
    "        ret = 0\n",
    "        for num in nums:\n",
    "            while num > 0:\n",
    "                if num & 1:\n",
    "                    ret += 1\n",
    "                num >>= 1\n",
    "        if max_num  > 0:\n",
    "            while max_num  > 0:\n",
    "                ret += 1\n",
    "                max_num  >>= 1\n",
    "            ret -= 1\n",
    "        \n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums) -> int:\n",
    "        add_count = 0\n",
    "        chen_count = 0\n",
    "        for num in nums :\n",
    "            if num == 0 :\n",
    "                continue\n",
    "            count = 0\n",
    "            val = num\n",
    "            while val > 1 :\n",
    "                odd = val % 2\n",
    "                val = val >> 1\n",
    "                count += 1\n",
    "                if odd :\n",
    "                    add_count += 1\n",
    "            add_count += 1\n",
    "            chen_count = max(chen_count,count)\n",
    "        return chen_count + add_count\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        maxn = max(nums)\n",
    "        ret = 0\n",
    "        for num in nums:\n",
    "            while num > 0:\n",
    "                if num & 1:\n",
    "                    ret += 1\n",
    "                num >>= 1\n",
    "        if maxn > 0:\n",
    "            while maxn > 0:\n",
    "                ret += 1\n",
    "                maxn >>= 1\n",
    "            ret -= 1\n",
    "        \n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        for item in nums:\n",
    "            while item>0:\n",
    "                if item%2==1:\n",
    "                    res+=1\n",
    "                item//=2\n",
    "        maxnum = max(nums)\n",
    "        if maxnum>0:\n",
    "            while maxnum>0:\n",
    "                res+=1\n",
    "                maxnum//=2\n",
    "            res-=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        la=[0] *31\n",
    "        for n in nums:\n",
    "            i=0\n",
    "            while n:\n",
    "                n,yu =divmod(n,2)\n",
    "                la[i]+=yu \n",
    "                i+=1\n",
    "        #倒序，是关键\n",
    "        j=30 \n",
    "        while j>-1 and la[j]==0:\n",
    "            j-=1\n",
    "        if j==-1:return 0\n",
    "        he=j\n",
    "        for w in range(j,-1,-1):\n",
    "            he+=la[w]\n",
    "        return he"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        maxn = max(nums).bit_length()\n",
    "        return maxn and maxn + sum(maxn.bit_count() for maxn in nums) - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        x = max(nums).bit_length()\n",
    "        if (sys.version_info.major, sys.version_info.minor) >= (3, 10):\n",
    "            return x and x + sum(x.bit_count() for x in nums) - 1\n",
    "        else:\n",
    "            return x and x + sum(bin(x).count('1') for x in nums) - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        la=[0] *31\n",
    "        for n in nums:\n",
    "            i=0\n",
    "            while n:\n",
    "                n,yu =divmod(n,2)\n",
    "                la[i]+=yu \n",
    "                i+=1\n",
    "        he =la[0]\n",
    "        f=0\n",
    "        #倒序，是关键\n",
    "        j=30 \n",
    "        while la[j]==0:\n",
    "            j-=1\n",
    "            if j==-1:return 0\n",
    "        he=j\n",
    "        for w in range(j,-1,-1):\n",
    "            he+=la[w]\n",
    "        return he"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        la=[0] *31\n",
    "        for n in nums:\n",
    "            for i in range(31):\n",
    "                la[i]+= 1&(n>>i)\n",
    "\n",
    "        #倒序，是关键\n",
    "        j=30 \n",
    "        while j>-1 and la[j]==0:\n",
    "            j-=1\n",
    "        if j==-1:return 0\n",
    "        he=j\n",
    "        for w in range(j,-1,-1):\n",
    "            he+=la[w]\n",
    "        return he"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        div_ = 0 # 除以2的次数\n",
    "        sub_ = 0 # -1的次数\n",
    "        for num in nums:\n",
    "            cur_div = 0\n",
    "            while num:\n",
    "                if num%2==0:\n",
    "                    num //=2\n",
    "                    cur_div += 1\n",
    "                else:\n",
    "                    num -= 1\n",
    "                    sub_ += 1\n",
    "            div_ = max(div_, cur_div)\n",
    "\n",
    "        return div_ + sub_\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        m,ans=0,0\n",
    "        for n in nums:\n",
    "            m=max(n,m)\n",
    "            while n:\n",
    "                if n&1:\n",
    "                    ans+=1\n",
    "                n>>=1\n",
    "        if m: ans-=1\n",
    "        while m:\n",
    "            ans+=1\n",
    "            m>>=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        h=b=big=0\n",
    "        for i in nums:\n",
    "            if i>b:\n",
    "                b=i\n",
    "            h+=i.bit_count()\n",
    "        if b==0:return 0\n",
    "        c =-1\n",
    "        while b:\n",
    "            b>>=1\n",
    "            c+=1 \n",
    "        return c+ h\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        # ans = 0\n",
    "        # n = len(nums)\n",
    "        # for i in range(31):\n",
    "        #     Flag = 0\n",
    "        #     for j in range(n):\n",
    "        #         ans += nums[j] & 1\n",
    "        #         nums[j] >>= 1\n",
    "        #         Flag += nums[j]\n",
    "        #     ans += 1\n",
    "        #     if Flag == 0:\n",
    "        #         return ans - 1\n",
    "        # return ans - 1\n",
    "\n",
    "        ans = 0 \n",
    "        maxcount = 0\n",
    "        for i in nums:\n",
    "            count = 0\n",
    "            while i > 0:\n",
    "                ans += i & 1\n",
    "                i >>= 1\n",
    "                count += 1\n",
    "            maxcount = max(maxcount,count)\n",
    "        return max(0,ans + maxcount - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        maxn = max(nums)\n",
    "        ret = 0\n",
    "        for num in nums:\n",
    "            while num > 0:\n",
    "                if num & 1:\n",
    "                    ret += 1\n",
    "                num >>= 1\n",
    "        if maxn > 0:\n",
    "            while maxn > 0:\n",
    "                ret += 1\n",
    "                maxn >>= 1\n",
    "            ret -= 1\n",
    "        \n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        cnt = ret = 0\n",
    "        for x in nums:\n",
    "            bit = len(bin(x)[2:]) - 1\n",
    "            cnt = max(cnt, bit)\n",
    "            ret += (x > 0) + (x - pow(2, bit)) * (x != pow(2, bit))\n",
    "        return (ret + cnt) % (10 ** 9 + 7)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        def dfs(x):\n",
    "            if x <= 1:\n",
    "                return x\n",
    "            return  x % 2 + dfs(x // 2)\n",
    "        ret = cnt = 0\n",
    "        for x in nums:\n",
    "            bit = len(bin(x)[2:]) - 1\n",
    "            cnt = max(cnt, bit)\n",
    "            ret += dfs(x)\n",
    "        return (ret + cnt) % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums) -> int:\n",
    "        plus_count = 0\n",
    "        max_multi_count = 0\n",
    "        for num in nums:\n",
    "            if num == 0:\n",
    "                continue\n",
    "            val = num\n",
    "            count = 0\n",
    "            while val > 1:\n",
    "                remain = val % 2\n",
    "                val = val >> 1\n",
    "                count += 1\n",
    "                if remain > 0:\n",
    "                    plus_count += 1\n",
    "            plus_count += 1\n",
    "            max_multi_count = max(max_multi_count, count)\n",
    "        return plus_count + max_multi_count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        mx = max(nums)\n",
    "        for x in nums:\n",
    "            while x > 0:\n",
    "                if x & 1:\n",
    "                    ans += 1\n",
    "                x >>= 1\n",
    "        if mx > 0:\n",
    "            while mx:\n",
    "                mx >>= 1\n",
    "                ans += 1\n",
    "            ans -= 1\n",
    "        return ans \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        ans=0\n",
    "        for v in nums:\n",
    "            ans+=v.bit_count()\n",
    "        a=max(nums)\n",
    "        if a==0: return ans\n",
    "        while a:\n",
    "            ans+=1\n",
    "            a>>=1\n",
    "        return ans-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        cnt = ret = 0\n",
    "        for x in nums:\n",
    "            bit = len(bin(x)[2:]) - 1\n",
    "            cnt = max(cnt, bit)\n",
    "            ret += (x > 0) + (x - pow(2, bit)) * (x != pow(2, bit))\n",
    "        return (ret + cnt) % (10 ** 9 + 7)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        def dfs(x):\n",
    "            if x <= 1:\n",
    "                return x\n",
    "            ret = x % 2 + dfs(x // 2)\n",
    "            return ret\n",
    "        ret = cnt = 0\n",
    "        for x in nums:\n",
    "            bit = len(bin(x)[2:]) - 1\n",
    "            cnt = max(cnt, bit)\n",
    "            ret += dfs(x)\n",
    "        return (ret + cnt) % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        maxn = max(nums)\n",
    "        ret = 0\n",
    "        for num in nums:\n",
    "            while num > 0:\n",
    "                if num & 1:\n",
    "                    ret += 1\n",
    "                num >>= 1\n",
    "        if maxn > 0:\n",
    "            while maxn > 0:\n",
    "                ret += 1\n",
    "                maxn >>= 1\n",
    "            ret -= 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        mx = max(nums)\n",
    "\n",
    "        for x in nums:\n",
    "            ans += x.bit_count() \n",
    "\n",
    "        ans += mx.bit_length()-1\n",
    "        return ans if mx  else 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        # 所有数中1比特的数量，加上最长数的位数-1\n",
    "        return sum(i.bit_count() for i in nums) + max(max(nums).bit_length() - 1, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        # 所有数中1比特的数量，加上最长数的位数-1\n",
    "        ans = sum(i.bit_count() for i in nums) + max(max(nums).bit_length() - 1, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        result = 0\n",
    "        for num in nums:\n",
    "            while num > 0:\n",
    "                if (num & 1) == 1:\n",
    "                    result += 1\n",
    "                num = (num >> 1)\n",
    "        maxn = max(nums)\n",
    "        while maxn > 1:\n",
    "            result += 1\n",
    "            maxn = (maxn >> 1)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        # ans = 0\n",
    "        # n = len(nums)\n",
    "        # for i in range(31):\n",
    "        #     Flag = 0\n",
    "        #     for j in range(n):\n",
    "        #         ans += nums[j] & 1\n",
    "        #         nums[j] >>= 1\n",
    "        #         Flag += nums[j]\n",
    "        #     ans += 1\n",
    "        #     if Flag == 0:\n",
    "        #         return ans - 1\n",
    "        # return ans - 1\n",
    "\n",
    "        # ans = 0 \n",
    "        # maxcount = 0\n",
    "        # for i in nums:\n",
    "        #     count = 0\n",
    "        #     while i > 0:\n",
    "        #         ans += i & 1\n",
    "        #         i >>= 1\n",
    "        #         count += 1\n",
    "        #     maxcount = max(maxcount,count)\n",
    "        # return max(0,ans + maxcount - 1)\n",
    "\n",
    "        ans = 0\n",
    "        maxcount = 0\n",
    "        for i in nums:\n",
    "            temp = bin(i)[2:]\n",
    "            ans += temp.count('1')\n",
    "            maxcount = max(maxcount,len(temp))\n",
    "        return max(0,ans + maxcount - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        cnt1 = 0\n",
    "        cnt2 = 0\n",
    "        for num in nums:\n",
    "            binval = bin(num)\n",
    "            l = len(binval) - 2\n",
    "            cnt1 += binval.count('1')\n",
    "            if l > 1:\n",
    "                cnt2 = max(cnt2, l-1)\n",
    "        return cnt1 + cnt2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "      maxVal = 0\n",
    "      cnt = 0\n",
    "      for num in nums:\n",
    "        maxVal = max(num, maxVal)\n",
    "        cnt += num.bit_count()\n",
    "      maxVal >>= 1\n",
    "      while maxVal:\n",
    "        cnt += 1\n",
    "        maxVal >>= 1\n",
    "      return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        cnt = ret = 0\n",
    "        for x in nums:\n",
    "            bit = len(bin(x)[2:]) - 1\n",
    "            cnt = max(cnt, bit)\n",
    "            ret += (x > 0) + (x - pow(2, bit)) * (x != pow(2, bit))\n",
    "        return (ret + cnt) % (10 ** 9 + 7)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int]) -> int:\n",
    "        def dfs(x):\n",
    "            if x <= 1:\n",
    "                return x\n",
    "            return x % 2 + dfs(x // 2)\n",
    "        ret = cnt = 0\n",
    "        for x in nums:\n",
    "            bit = len(bin(x)[2:]) - 1\n",
    "            cnt = max(cnt, bit)\n",
    "            ret += dfs(x)\n",
    "        return ret + cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], k: int) -> int:\n",
    "        seen: list[bool] = [False] * (k + 1)\n",
    "        n_left: int = k\n",
    "        i: int = len(nums) - 1\n",
    "        n_ops: int = 0\n",
    "\n",
    "        while n_left > 0:\n",
    "            if nums[i] <= k and not seen[nums[i]]:\n",
    "                seen[nums[i]] = True\n",
    "                n_left -= 1\n",
    "            i -= 1\n",
    "            n_ops += 1\n",
    "        \n",
    "        return n_ops"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], k: int) -> int:\n",
    "        visited = set()\n",
    "        for i in range(len(nums)-1,-1,-1):\n",
    "            if nums[i]<=k:\n",
    "                visited.add(nums[i])\n",
    "            \n",
    "            if len(visited)==k:\n",
    "                return len(nums)-i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], k: int) -> int:\n",
    "        t=0\n",
    "        res=set()\n",
    "        for c,i in enumerate(nums[::-1]):\n",
    "            if i<=k and i not in res:\n",
    "                res.add(i)\n",
    "                t+=1\n",
    "                if t==k:\n",
    "                    return c+1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], k: int) -> int:\n",
    "        t=0\n",
    "        res=set()\n",
    "        for c,i in enumerate(nums[::-1]):\n",
    "            if i<=k and i not in res:\n",
    "                res.add(i)\n",
    "                t+=1\n",
    "                if t==k:\n",
    "                    return c+1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "子序列----和顺序无关\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], target: int) -> int:\n",
    "        if sum(nums)<target:\n",
    "            return -1\n",
    "        \n",
    "        cnt=Counter(nums)\n",
    "        i=0\n",
    "        ans=0\n",
    "        s=0 ##低位  数之和\n",
    "        while(1<<i <=target):\n",
    "            s+=cnt[1<<i] <<i   ##  第i位的数的个数 *第i位的数    e.g. i==3  cnt[8]==2   s+= cnt[8]*8==s+=16\n",
    "            mask=(1<<(i+1))-1 \n",
    "            if s>=target&mask:  ##小于i的低位二进制    都可以由比较小的位数和构成\n",
    "                i+=1\n",
    "                continue\n",
    "\n",
    "\n",
    "            ans+=1 ##找大数分割\n",
    "            i+=1\n",
    "            while(cnt[1<<i]==0):\n",
    "                ans+=1  ##持续找大数\n",
    "                i+=1  ##位数+1\n",
    "\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], target: int) -> int:\n",
    "        if sum(nums) < target: return -1\n",
    "        \n",
    "        c = Counter(nums)\n",
    "        ans = s = i = 0\n",
    "\n",
    "        while target >= (1 << i):\n",
    "            s += c[(1 << i)] << i\n",
    "            mask = (1 << (i + 1)) - 1\n",
    "            i += 1\n",
    "            if s >=  mask & target:\n",
    "                continue\n",
    "            \n",
    "            ans += 1\n",
    "            while c[1 << i] == 0:\n",
    "                ans += 1\n",
    "                i += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], target: int) -> int:\n",
    "        # if sum(nums) < target:\n",
    "        #     return -1\n",
    "        # cnt = Counter(nums)\n",
    "        # print(cnt)\n",
    "        # ans = s = i = 0\n",
    "        # while 1 << i <= target:\n",
    "        #     s += cnt[1 << i] << i\n",
    "        #     mask = (1 << (i + 1)) - 1\n",
    "        #     i += 1\n",
    "        #     print(target,mask)\n",
    "        #     print(target & mask)\n",
    "        #     if s >= target & mask:\n",
    "        #         continue\n",
    "        #     ans += 1  # 一定要找更大的数操作\n",
    "        #     while cnt[1 << i] == 0:\n",
    "        #         ans += 1  # 还没找到，继续找更大的数\n",
    "        #         i += 1\n",
    "        # return ans\n",
    "        if sum(nums) < target:\n",
    "            return -1\n",
    "        cnt = Counter(nums)\n",
    "        ans = 0\n",
    "        sums = 0\n",
    "        i = 0\n",
    "        while 1 << i <= target:\n",
    "            sums += cnt[1<<i]  << i\n",
    "            mark = (1 << (i+1)) - 1\n",
    "            i += 1\n",
    "            if sums >= target & mark:\n",
    "                continue\n",
    "            ans += 1\n",
    "            while cnt[1<<i] == 0:\n",
    "                i += 1\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], target: int) -> int:\n",
    "        if sum(nums) < target:\n",
    "            return -1\n",
    "        cnt = Counter(nums)\n",
    "        ans = s = i = 0\n",
    "        while 1 << i <= target:\n",
    "            s += cnt[1 << i] << i\n",
    "            mask = (1 << (i + 1)) - 1\n",
    "            i += 1\n",
    "            if s >= target & mask:\n",
    "                continue\n",
    "            ans += 1\n",
    "            while cnt[1 << i] == 0:\n",
    "                ans += 1\n",
    "                i += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], target: int) -> int:\n",
    "        # li = [0] * 32\n",
    "        # ans, sumNum, idx, tailIdx, lastIdx = 0, 0, 0, 0, -1\n",
    "        \n",
    "        # for num in nums:\n",
    "        #     i = int(math.log2(num))\n",
    "        #     tailIdx = max(tailIdx, i)\n",
    "        #     li[i] += 1\n",
    "        \n",
    "        # while target:\n",
    "        #     sumNum = (sumNum >> 1) + li[idx]\n",
    "        #     if target & 1:\n",
    "        #         if sumNum: sumNum -= 1\n",
    "        #         elif lastIdx == -1: lastIdx = idx\n",
    "        #     if sumNum > 0 and lastIdx > -1:\n",
    "        #         ans += idx - lastIdx\n",
    "        #         lastIdx = -1\n",
    "        #         sumNum -= 1\n",
    "        #     target >>= 1\n",
    "        #     idx += 1\n",
    "        \n",
    "        # if target > 0 or idx > tailIdx and lastIdx > -1: return -1\n",
    "        # if lastIdx == -1: return ans\n",
    "        \n",
    "        # while li[idx] == 0: idx += 1\n",
    "        # return ans + idx - lastIdx\n",
    "        \n",
    "\n",
    "        # \n",
    "        if sum(nums) < target:\n",
    "            return -1\n",
    "        counter = Counter(nums)\n",
    "        cnts = [0] * 33\n",
    "        res = 0\n",
    "\n",
    "        for i in range(32):\n",
    "            num = 1 << i\n",
    "            if (target & num) != 0:\n",
    "                cnts[i] -= 1\n",
    "            if counter[num] != 0:\n",
    "                cnts[i] += counter[num]\n",
    "            carry = cnts[i] // 2\n",
    "            cnts[i + 1] += carry\n",
    "            if carry < 0:\n",
    "                res -= carry\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], target: int) -> int:\n",
    "        if sum(nums) < target: return -1\n",
    "        cnt = Counter(nums)\n",
    "        ans = s = i = 0\n",
    "        while 1 << i <= target:\n",
    "            s += cnt[1<<i]<< i \n",
    "            mask = (1<<(i+1)) - 1\n",
    "            i += 1\n",
    "            if s >= target & mask:\n",
    "                continue\n",
    "            ans += 1\n",
    "            while cnt[1<<i] == 0:\n",
    "                ans += 1\n",
    "                i += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], target: int) -> int:\n",
    "        t = []\n",
    "        while target:\n",
    "            if target & 1:\n",
    "                t.append(1)\n",
    "            else:\n",
    "                t.append(0)\n",
    "            target >>= 1\n",
    "        nums = [int(math.log(x, 2)) for x in nums]\n",
    "        heapify(nums)\n",
    "        spop = set()\n",
    "        # print(nums, t)\n",
    "\n",
    "        ans = 0\n",
    "        for i, x in enumerate(t):\n",
    "            if x == 0: continue\n",
    "            while nums and nums[0] < i:\n",
    "                y = nums[0]\n",
    "                heappop(nums)\n",
    "                while y in spop:\n",
    "                    spop.remove(y)\n",
    "                    y += 1\n",
    "                if y >= i:\n",
    "                    heappush(nums, y)\n",
    "                else:\n",
    "                    spop.add(y)\n",
    "            while nums and nums[0] > i:\n",
    "                y = nums[0]\n",
    "                heappop(nums)\n",
    "                y -= 1\n",
    "                ans += 1\n",
    "                heappush(nums, y)\n",
    "                heappush(nums, y)\n",
    "            if len(nums) == 0:\n",
    "                return -1\n",
    "            heappop(nums)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], target: int) -> int:\n",
    "        if sum(nums) < target:\n",
    "            return -1\n",
    "        cnt = Counter(nums)\n",
    "        ans = s = i = 0\n",
    "        while 1 << i <= target:\n",
    "            s += cnt[1 << i] << i\n",
    "            mask = (1 << (i + 1)) - 1\n",
    "            i += 1\n",
    "            if s >= target & mask:\n",
    "                continue\n",
    "            ans += 1  # 一定要找更大的数操作\n",
    "            while cnt[1 << i] == 0:\n",
    "                ans += 1  # 还没找到，继续找更大的数\n",
    "                i += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], target: int) -> int:\n",
    "        if sum(nums) < target:\n",
    "            return -1\n",
    "        cnt = Counter(nums)\n",
    "        ans = s = 0\n",
    "        for i in range(31):\n",
    "            s += cnt[1 << i] << i\n",
    "            if (target >> i & 1) == 0:\n",
    "                continue\n",
    "            s -= 1 << i  # 先减掉\n",
    "            if s >= 0:\n",
    "                continue\n",
    "            for j in range(i + 1, 31):\n",
    "                if cnt[1 << j]:\n",
    "                    ans += j - i\n",
    "                    cnt[1 << j] -= 1\n",
    "                    s += 1 << j  # 从 i 到 j 都至少有一个 1，都满足要求，可以直接加到 s 中\n",
    "                    break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], target: int) -> int:\n",
    "        total = sum(nums)\n",
    "        if total < target:\n",
    "            return -1\n",
    "        cnt = Counter(nums)\n",
    "        res = 0\n",
    "        for i in range(31):\n",
    "            if target & (1 << i):\n",
    "                cnt[1 << i] -= 1\n",
    "            temp = cnt[1 << i] // 2\n",
    "            if temp < 0:\n",
    "                res -= temp\n",
    "            cnt[1 << (i + 1)] += temp\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], target: int) -> int:\n",
    "        t = bin(target)[2:]\n",
    "        d = [0]*33\n",
    "        \n",
    "        \n",
    "        for x in nums:\n",
    "            d[int(log2(x))] += 1\n",
    "        # print(d)\n",
    "        for i, ch in enumerate(t[::-1]):\n",
    "            d[i] -= int(ch)        \n",
    "        print(d)\n",
    "        \n",
    "        \n",
    "        # for i in range(32):\n",
    "        #     if 2**i > target: break\n",
    "        #     if d[i] >= 2:\n",
    "        #         d[i+1] += d[i]//2\n",
    "        #         d[i] = d[i]%2\n",
    "        # print(d)\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(32):\n",
    "            while d[i] < 0:\n",
    "                # add\n",
    "                for j in range(i):\n",
    "                    if d[j] >= 2:\n",
    "                        d[j+1] += d[j]//2\n",
    "                        d[j] = d[j]%2\n",
    "                if d[i] >= 0: break\n",
    "                # drop\n",
    "                cannot = True\n",
    "                for j in range(i+1, 32):\n",
    "                    # print(j, end=', ')\n",
    "                    if d[j] > 0:\n",
    "                        cannot = False\n",
    "                        d[j] -= 1\n",
    "                        ans += 1\n",
    "                        d[j-1] += 2\n",
    "                        # print(2**j, 2**(j-1))\n",
    "                        # print(d)\n",
    "                        break\n",
    "                if cannot: return -1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], target: int) -> int:\n",
    "        if sum(nums) < target:\n",
    "            return -1\n",
    "        s = i = ans = 0\n",
    "        cnt = Counter(nums)\n",
    "        while 1 << i <= target:\n",
    "            s += cnt[1<<i] * 1 << i\n",
    "            f = (1 << (i + 1)) -1\n",
    "            i += 1\n",
    "            if s >= f&target:  \n",
    "                continue\n",
    "            ans += 1\n",
    "            while cnt[1 << i] == 0:\n",
    "                i += 1\n",
    "                ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], target: int) -> int:\n",
    "        l = len(nums)\n",
    "        \n",
    "        l_t = target.bit_length()\n",
    "        l_m = max(nums).bit_length()\n",
    "        l_1 = max(l_t, l_m)\n",
    "        target_power = [0] * l_1\n",
    "        for i in range(l_1):\n",
    "            target_power[i] = (target & 1)\n",
    "            target >>= 1\n",
    "        \n",
    "        nums_power = [0] * l_1\n",
    "        for i in nums:\n",
    "            nums_power[int(math.log(i, 2))] += 1\n",
    "        print(target_power)\n",
    "        print(nums_power)\n",
    "        ans = 0\n",
    "        for i in range(l_1):\n",
    "            if target_power[i] == 0:\n",
    "                if i + 1 <= l_1 - 1:\n",
    "                    nums_power[i + 1] += nums_power[i] // 2\n",
    "                    nums_power[i] = nums_power[i] % 2\n",
    "            else:\n",
    "                if nums_power[i] > 0:\n",
    "                    nums_power[i] -= 1\n",
    "                    target_power[i] -= 1\n",
    "                    if i + 1 <= l_1 - 1:\n",
    "                        nums_power[i + 1] += nums_power[i] // 2\n",
    "                        nums_power[i] = nums_power[i] % 2 \n",
    "                else:\n",
    "                    pointer = i\n",
    "                    flag = False\n",
    "                    while pointer < l_m:\n",
    "                        if nums_power[pointer] <= 0:\n",
    "                            nums_power[pointer] += 1\n",
    "                            pointer += 1\n",
    "                            #print(pointer)\n",
    "                        else:\n",
    "                            flag = True\n",
    "                            break\n",
    "                    if flag == False:\n",
    "                        return -1\n",
    "                    ans += pointer - i\n",
    "                    nums_power[pointer] -= 1\n",
    "                    nums_power[i] -= 1\n",
    "                    target_power[i] -= 1\n",
    "            print(target_power, nums_power)\n",
    "        return ans\n",
    "                    \n",
    "\n",
    "                    \n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "        \n",
    "\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], target: int) -> int:\n",
    "        if sum(nums)<target:\n",
    "            return -1\n",
    "        \n",
    "        cnt = Counter(nums)\n",
    "        ans = s = i = 0\n",
    "        while 1 << i <= target:\n",
    "            #2^i\n",
    "            #cnt[1<<i] -> 2^i的数量\n",
    "            # s+= cnt[1<<i] * 2^i\n",
    "            s += cnt[1<<i] <<i\n",
    "            \n",
    "            #mask = 011111111\n",
    "            mask = (1<<(i+1))-1\n",
    "            i+=1\n",
    "            #如果target的后i位可以被组合出来\n",
    "            if s >= target & mask:\n",
    "                continue\n",
    "            \n",
    "            ans+=1 #需要分割操作\n",
    "            while cnt[1<<i] == 0:\n",
    "                ans += 1 #在分割到1<<i之前需要再分割一次\n",
    "                i += 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], target: int) -> int:\n",
    "        if sum(nums) < target:\n",
    "            return -1\n",
    "        cnt = Counter(nums)\n",
    "        ans = s = i = 0\n",
    "        while 1 << i <= target:\n",
    "            s += cnt[1 << i] << i\n",
    "            mask = (1 << (i + 1)) - 1\n",
    "            i += 1\n",
    "            if s >= target & mask:\n",
    "                continue\n",
    "            ans += 1  # 一定要找更大的数操作\n",
    "            while cnt[1 << i] == 0:\n",
    "                ans += 1  # 还没找到，继续找更大的数\n",
    "                i += 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], target: int) -> int:\n",
    "        if sum(nums) < target: return -1\n",
    "        cnt = Counter(nums)\n",
    "        ans = 0\n",
    "        # smaller_numbers 记录所有更小的次幂的数的和\n",
    "        smaller_numbers = 0\n",
    "        for i in range(31):\n",
    "            # 先加上当前次幂的数值\n",
    "            smaller_numbers += cnt[1 << i] << i\n",
    "            if target >> i & 1:\n",
    "                # 如果更小的数之和是大于当前要表示的比特位，那么不需要进行操作\n",
    "                if smaller_numbers >= 1 << i:\n",
    "                    smaller_numbers -= 1 << i\n",
    "                else:\n",
    "                    # 否则寻找最小的更大的 2 的次幂\n",
    "                    for j in range(i + 1, 31):\n",
    "                        if cnt[1 << j]:\n",
    "                            cnt[1 << j] -= 1\n",
    "                            smaller_numbers += 1 << j\n",
    "                            smaller_numbers -= 1 << i\n",
    "                            ans += j - i\n",
    "                            break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], target: int) -> int:\n",
    "        if sum(nums)<target:\n",
    "            return -1\n",
    "        cnt=Counter(nums)\n",
    "        ans=s=i=0\n",
    "        while 1<<i<=target:\n",
    "            s+=cnt[1<<i]<<i\n",
    "            mask=(1<<(i+1))-1\n",
    "            if s>=target&mask:\n",
    "                i+=1\n",
    "                continue\n",
    "            i+=1\n",
    "            ans+=1\n",
    "            while cnt[1<<i]==0:\n",
    "                ans+=1\n",
    "                i+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], target: int) -> int:\n",
    "        d = [int(log2(i)) for i in nums]\n",
    "        d = Counter(d)\n",
    "        res = 0\n",
    "        for i in range(32):\n",
    "            if target & (1 << i) == 0:\n",
    "                d[i + 1] += d[i] // 2\n",
    "                continue\n",
    "            if d[i] == 0:\n",
    "                print(i)\n",
    "                j = i + 1\n",
    "                while d[j] == 0 and j < 33:\n",
    "                    j += 1\n",
    "                if j == 33:\n",
    "                    return -1\n",
    "                p = 1\n",
    "                for k in range(i, j):\n",
    "                    d[k] += 1\n",
    "                    res += 1\n",
    "                d[j] -= 1\n",
    "            else:\n",
    "                d[i] -= 1\n",
    "                d[i + 1] += d[i] // 2\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], target: int) -> int:\n",
    "        if sum(nums) < target:\n",
    "            return -1 \n",
    "        cnt = Counter(nums)\n",
    "        #print(sorted(nums)) \n",
    "        s = i = 0 \n",
    "        ans = 0 \n",
    "        while i < 32:\n",
    "            s += cnt[1<<i] * (1<<i) \n",
    "            if (target >> i) & 1 == 0:\n",
    "                i+=1\n",
    "                continue \n",
    "            if s >= (1 << i):\n",
    "                s -= 1 << i \n",
    "                i+=1\n",
    "                continue \n",
    "            ans += 1\n",
    "            s = 0 \n",
    "            i += 1\n",
    "            while i < 32 and cnt[1<<i] == 0:\n",
    "                i+=1\n",
    "                ans += 1 \n",
    "            cnt[1<<i] -= 1\n",
    "\n",
    "        return ans \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], target: int) -> int:\n",
    "        if sum(nums) < target:\n",
    "            return -1\n",
    "        cnt = Counter(nums)\n",
    "        ans = s = i = 0\n",
    "        while 1 << i <= target:\n",
    "            s += cnt[1 << i] << i\n",
    "            mask = (1 << (i + 1)) - 1\n",
    "            i += 1\n",
    "            if s >= target & mask:\n",
    "                continue\n",
    "            ans += 1  # 一定要找更大的数操作\n",
    "            while cnt[1 << i] == 0:\n",
    "                ans += 1  # 还没找到，继续找更大的数\n",
    "                i += 1\n",
    "        return ans\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        s = 0\n",
    "        lowbit = (target & (-target))\n",
    "        ans = 0\n",
    "        for v in nums:\n",
    "            if v > lowbit:\n",
    "                ans += v.bit_length() - lowbit.bit_length()\n",
    "                while lowbit < v:\n",
    "                    target -= lowbit\n",
    "                    if not target:\n",
    "                        break\n",
    "                    lowbit = (target & (-target))\n",
    "            else:\n",
    "                s += v\n",
    "                while lowbit <= s:\n",
    "                    s -= lowbit\n",
    "                    target -= lowbit\n",
    "                    if not target:\n",
    "                        break\n",
    "                    lowbit = (target & (-target))\n",
    "            if not target:\n",
    "                break\n",
    "        if target:\n",
    "            return -1\n",
    "        else:\n",
    "            return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], t: int) -> int:\n",
    "        \n",
    "        if sum(nums) < t:\n",
    "            return -1\n",
    "        \n",
    "        cnt = Counter(nums)\n",
    "        \n",
    "        i = s = res = 0\n",
    "        while (1 << i) <= t:\n",
    "            s += cnt[1 << i] << i\n",
    "            mask = (1 << (i + 1)) - 1\n",
    "            \n",
    "            if s >= t & mask:\n",
    "                i += 1\n",
    "                continue\n",
    "            \n",
    "            res += 1\n",
    "            i += 1\n",
    "            while cnt[1 << i] == 0:\n",
    "                i += 1\n",
    "                res += 1\n",
    "        return res\n",
    "            \n",
    "                    \n",
    "                    \n",
    "                    \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import *\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], target: int) -> int:\n",
    "        if sum(nums) < target:\n",
    "            return -1\n",
    "        res, pres = 0, 1\n",
    "        heapify(nums)\n",
    "        while nums and pres <= target:\n",
    "            if pres & target:\n",
    "                while len(nums) >= 2 and nums[0] < pres:\n",
    "                    npres1 = heappop(nums)\n",
    "                    npres2 = heappop(nums)\n",
    "                    if npres1 == npres2:\n",
    "                        heappush(nums, npres1 << 1)\n",
    "                    else:\n",
    "                        heappush(nums, npres2)\n",
    "                if nums[0] == pres:\n",
    "                    heappop(nums)\n",
    "                elif nums[0] > pres:\n",
    "                    npres = heappop(nums)\n",
    "                    while npres > pres:\n",
    "                        npres >>= 1\n",
    "                        heappush(nums, npres)\n",
    "                        res += 1\n",
    "                else:\n",
    "                    return -1\n",
    "            pres <<= 1\n",
    "        return res if pres > target else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], target: int) -> int:\n",
    "        if sum(nums) < target:\n",
    "            return -1\n",
    "        cnt = Counter(nums)\n",
    "        ans = s = i = 0\n",
    "        while 1 << i <= target:\n",
    "            s += cnt[1 << i] << i\n",
    "            mask = (1 << (i + 1)) - 1\n",
    "            i += 1\n",
    "            if s >= target & mask:\n",
    "                continue\n",
    "            ans += 1  # 一定要找更大的数操作\n",
    "            while cnt[1 << i] == 0:\n",
    "                ans += 1  # 还没找到，继续找更大的数\n",
    "                i += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], target: int) -> int:\n",
    "        if sum(nums) < target:\n",
    "            return -1\n",
    "        \n",
    "        cnt = Counter(nums)\n",
    "        ans = s = i = 0\n",
    "\n",
    "        while 1 << i <= target:\n",
    "            s += cnt[1 << i] << i\n",
    "            mask = (1 << (i + 1)) - 1\n",
    "            i += 1\n",
    "            if s >= target & mask:\n",
    "                continue\n",
    "            ans += 1\n",
    "            while cnt[1<<i] == 0:\n",
    "                ans += 1\n",
    "                i += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        if sum(nums) < target:\n",
    "            return - 1\n",
    "        nums.sort(reverse = True)\n",
    "        res = 0\n",
    "        for i in range(32):\n",
    "            s = 0\n",
    "            if target & (1 << i):\n",
    "                x = 1 << i \n",
    "                while nums and nums[-1] < x and s < x:\n",
    "                    s += nums.pop()\n",
    "                if s >= x:\n",
    "                    s -= x \n",
    "                elif nums[-1] == x:\n",
    "                    nums.pop()\n",
    "                else:\n",
    "                    last = nums.pop()\n",
    "                    while last > x:\n",
    "                        last //= 2 \n",
    "                        nums.append(last)\n",
    "                        res += 1 \n",
    "        return res \n",
    "\n",
    "      \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        if sum(nums) < target:\n",
    "            return - 1\n",
    "        nums.sort(reverse = True)\n",
    "        res = 0\n",
    "        cursum = 0\n",
    "        for i in range(32):\n",
    "            if target & 1 << i:\n",
    "                x = 1 << i \n",
    "                while nums and cursum < x and nums[-1] < x:\n",
    "                    cursum += nums.pop()\n",
    "                if cursum >= x:\n",
    "                    cursum -= x \n",
    "                elif nums[-1] == x:\n",
    "                    nums.pop()\n",
    "                else:\n",
    "                    last = nums.pop()\n",
    "                    while last > x:\n",
    "                        last //= 2 \n",
    "                        nums.append(last)\n",
    "                        res += 1 \n",
    "        return res \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], t: int) -> int:\n",
    "        s = sum(nums)\n",
    "        if s < t: return -1\n",
    "        ans = 0\n",
    "        nums.sort()\n",
    "\n",
    "        while t:\n",
    "            v = nums.pop()\n",
    "            if s - v >= t:\n",
    "                s -= v\n",
    "            elif v <= t:\n",
    "                t -= v\n",
    "                s -= v\n",
    "            else:\n",
    "                ans += 1\n",
    "                \"\"\"\n",
    "                剩下的sum() < t 且 v > t，那显然max(剩下的数) < v\n",
    "                所以必然v // 2 >= max(剩下的数)\n",
    "                \"\"\"\n",
    "                nums.append(v // 2)\n",
    "                nums.append(v // 2)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], target: int) -> int:\n",
    "        if sum(nums) < target:\n",
    "            return -1\n",
    "        cnt = Counter(nums)\n",
    "        ans = s = i = 0\n",
    "        while 1 << i <= target:\n",
    "            s += cnt[1 << i] << i\n",
    "            mask = (1 << (i + 1)) - 1\n",
    "            i += 1\n",
    "            if s >= target & mask:\n",
    "                continue\n",
    "            ans += 1  # 一定要找更大的数操作\n",
    "            while cnt[1 << i] == 0:\n",
    "                ans += 1  # 还没找到，继续找更大的数\n",
    "                i += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], target: int) -> int:\n",
    "        if sum(nums) < target:\n",
    "            return -1\n",
    "        if sum(nums) == target:\n",
    "            return 0\n",
    "        \n",
    "        cnt = Counter(nums)\n",
    "        ans = i = s = 0\n",
    "        while 1 << i <= target:\n",
    "            s += cnt[1<<i] * (1 << i)\n",
    "            mask = (1 << (i+1)) - 1\n",
    "            if s >= target&mask:\n",
    "                i += 1\n",
    "                continue\n",
    "            i += 1\n",
    "            ans += 1\n",
    "            while cnt[1 << i] == 0:\n",
    "                ans += 1\n",
    "                i += 1\n",
    "            \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], target: int) -> int:\n",
    "        tot = sum(nums)\n",
    "        if tot < target:\n",
    "            return -1\n",
    "        res = 0\n",
    "        nums.sort()\n",
    "        while target:\n",
    "            t = nums.pop()\n",
    "            if tot - t >= target:\n",
    "                tot -= t\n",
    "            elif t > target:\n",
    "                res += 1\n",
    "                nums.append(t >> 1)\n",
    "                nums.append(t >> 1)\n",
    "            else:\n",
    "                target -= t\n",
    "                tot -= t\n",
    "        return res\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], target: int) -> int:\n",
    "        if sum(nums) < target:\n",
    "            return -1\n",
    "        # 枚举target的每一位\n",
    "        i = 0\n",
    "        s = 0\n",
    "        ans = 0\n",
    "        cnt = Counter(nums)\n",
    "        while (1<<i) <= target:\n",
    "            s += cnt[(1<<i)]*(1<<i)\n",
    "            mask = (1 << (i+1))-1\n",
    "            # 可以凑出来\n",
    "            if s >= target&mask:\n",
    "                i += 1\n",
    "                continue\n",
    "            # 不能凑出来\n",
    "            ans += 1\n",
    "            i += 1\n",
    "            while cnt[1<<i] == 0:\n",
    "                i += 1\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], target: int) -> int:\n",
    "        count = 0\n",
    "        nums.sort()\n",
    "        total_nums = sum(nums)\n",
    "        if total_nums < target:\n",
    "            return -1\n",
    "        elif total_nums == target:\n",
    "            return 0\n",
    "        else:\n",
    "            while target:\n",
    "                a = nums.pop()\n",
    "                if total_nums - a >= target:\n",
    "                    total_nums -= a\n",
    "                elif a >target:\n",
    "                    count += 1\n",
    "                    nums.append(a / 2)\n",
    "                    nums.append(a / 2)\n",
    "                else:\n",
    "                    target -= a\n",
    "                    total_nums -= a\n",
    "            return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], tar: int) -> int:\n",
    "      nums.sort()\n",
    "      tot = sum(nums)\n",
    "      res = 0\n",
    "      while len(nums) != 0 and tar != 0:\n",
    "        t = nums.pop()\n",
    "        if tot - t >= tar:\n",
    "          tot -= t\n",
    "        elif t <= tar:\n",
    "          tot -= t\n",
    "          tar -= t\n",
    "        else:\n",
    "          nums.append(t / 2)\n",
    "          nums.append(t / 2)\n",
    "          res += 1\n",
    "      if tar != 0:\n",
    "        return -1\n",
    "      else:\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], target: int) -> int:\n",
    "        numsSum = sum(nums)\n",
    "        if target>numsSum:\n",
    "            return -1\n",
    "        nums.sort()\n",
    "        \n",
    "        res = 0\n",
    "\n",
    "        while target:\n",
    "            big = nums.pop()\n",
    "            if numsSum-big>=target:\n",
    "                numsSum-=big\n",
    "            elif big>target:\n",
    "                res += 1\n",
    "                nums.append(big//2)\n",
    "                nums.append(big//2)\n",
    "            else:\n",
    "                target -= big\n",
    "                numsSum -= big\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], target: int) -> int:\n",
    "        if sum(nums) < target:\n",
    "            return -1\n",
    "        cnt = Counter(nums)\n",
    "        ans = s = i = 0\n",
    "        while 1 << i <= target:\n",
    "            s += cnt[1 << i] << i\n",
    "            mask = (1 << (i + 1)) - 1\n",
    "            i += 1\n",
    "            if s >= target & mask:\n",
    "                continue\n",
    "            ans += 1  # 一定要找更大的数操作\n",
    "            while cnt[1 << i] == 0:\n",
    "                ans += 1  # 还没找到，继续找更大的数\n",
    "                i += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], target: int) -> int:\n",
    "        if sum(nums)<target:return -1\n",
    "        ans=s=0\n",
    "        cnt=Counter(nums)\n",
    "        i=0\n",
    "        while(1<<i <=target):\n",
    "            s+=cnt[1<<i]<<i\n",
    "            mask=(1<<(i+1))-1\n",
    "            if s>=target&mask:\n",
    "                i+=1\n",
    "                continue\n",
    "            \n",
    "            ##拆分\n",
    "            ans+=1\n",
    "            i+=1\n",
    "            while(cnt[1<<i]==0):\n",
    "                i+=1\n",
    "                ans+=1\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], target: int) -> int:\n",
    "        if sum(nums)<target:\n",
    "            return -1\n",
    "\n",
    "        target = list(map(int, bin(target)[2:]))[::-1]\n",
    "        tmp = [0] * max(len(target), int(math.log2(max(nums))+1))\n",
    "        for n in nums:\n",
    "            tmp[int(math.log2(n))]+=1\n",
    "        nums = tmp\n",
    "        for i in range(len(target)):\n",
    "            nums[i] -= target[i]\n",
    "        last = None\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] < 0 and last is None:\n",
    "                last = i\n",
    "            if nums[i] > 0 and last is not None:\n",
    "                nums[i] -= 1\n",
    "                ans += i-last\n",
    "                last = None\n",
    "            if nums[i] > 1 and i+1 < len(nums):\n",
    "                tmp = nums[i]//2\n",
    "                nums[i] -= 2*tmp\n",
    "                nums[i+1] += tmp\n",
    "            \n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def minOperations(self, nums: List[int], target: int) -> int:\n",
    "        h = [num.bit_length() - 1 for num in nums]\n",
    "        heapify(h)\n",
    "        ans = 0\n",
    "        pre = -1\n",
    "        for i in range(target.bit_length()):\n",
    "            if target & (1 << i):\n",
    "                if not h:\n",
    "                    return -1\n",
    "                while h:\n",
    "                    v = heappop(h)\n",
    "                    if v >= i:\n",
    "                        ans += v - i\n",
    "                        for j in range(i + 1, v):\n",
    "                            heappush(h, j)\n",
    "                        break\n",
    "                    else:\n",
    "                        if v == pre:\n",
    "                            heappush(h, v + 1)\n",
    "                            pre = -1\n",
    "                        else:\n",
    "                            pre = v\n",
    "                else:\n",
    "                    return -1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], target: int) -> int:\n",
    "        sm = sum(nums)\n",
    "        if sm < target:\n",
    "            return -1\n",
    "        nums.sort()\n",
    "        op = 0\n",
    "        while target:\n",
    "            a = nums.pop()\n",
    "            if sm - a >= target:\n",
    "                sm -= a\n",
    "            elif a <= target:\n",
    "                sm -= a\n",
    "                target -= a\n",
    "            else:\n",
    "                nums += [a//2,a//2]\n",
    "                op += 1\n",
    "\n",
    "        return op"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], target: int) -> int:\n",
    "        sum = 0\n",
    "        a = [0]*32\n",
    "        for i in nums:\n",
    "            sum += i\n",
    "            a[int(math.log(i,2))] += 1\n",
    "        if sum<target:\n",
    "            return -1\n",
    "        bina = [0]*32\n",
    "        res, t = 0, 0\n",
    "        while target:\n",
    "            bina[t] = target%2\n",
    "            t += 1\n",
    "            target//=2\n",
    "\n",
    "        for i in range(31):\n",
    "            if a[i]<bina[i]:\n",
    "                res += 1\n",
    "                a[i+1] -= 1\n",
    "            else :\n",
    "                a[i+1] += (a[i]-bina[i])//2\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], target: int) -> int:\n",
    "        ls=[4294967296, 2147483648, 1073741824, 536870912, 268435456, 134217728, 67108864, 33554432, 16777216, 8388608, 4194304, 2097152, 1048576, 524288, 262144, 131072, 65536, 32768, 16384, 8192, 4096, 2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1]\n",
    "        m=sum(nums)\n",
    "        if m==target:\n",
    "            return 0\n",
    "        if m<target:\n",
    "            return -1\n",
    "        c=collections.Counter(nums)\n",
    "        tar=collections.Counter()\n",
    "        i=0\n",
    "        maxtar=-1\n",
    "        while target>0:\n",
    "            if target<ls[i]:\n",
    "                i+=1\n",
    "                continue\n",
    "            target-=ls[i]\n",
    "            if maxtar==-1:\n",
    "                maxtar=ls[i]\n",
    "            tar[ls[i]]+=1\n",
    "            i+=1\n",
    "        i=1\n",
    "        count=0\n",
    "        #print(tar,c)\n",
    "        while i<=maxtar:\n",
    "            c[i]+=c[i//2]//2\n",
    "            #print(i,c[i],tar[i],c)\n",
    "            if c[i]>=tar[i]:\n",
    "                c[i]-=tar[i]\n",
    "                #print(i,c[i])\n",
    "            else:\n",
    "                tp=i\n",
    "                while c[tp]==0:\n",
    "                    tp*=2\n",
    "                    count+=1\n",
    "                j=i \n",
    "                while j<tp:\n",
    "                    c[j]+=1\n",
    "                    j*=2\n",
    "                c[tp]-=1\n",
    "            i*=2\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], target: int) -> int:\n",
    "        if sum(nums)<target:\n",
    "            return -1\n",
    "        cnt=Counter(nums)\n",
    "        temp=[0]*33\n",
    "        ans=0\n",
    "        i=0\n",
    "        while i<32:\n",
    "            num=1<<i\n",
    "            if (target&num)!=0:\n",
    "                temp[i]-=1\n",
    "            if cnt[num]>0:\n",
    "                temp[i]+=cnt[num]\n",
    "            if temp[i]<0:\n",
    "                j=i\n",
    "                while (cnt[1<<j])==0:\n",
    "                    temp[j]+=1\n",
    "                    j+=1\n",
    "                    ans+=1\n",
    "                temp[j]=cnt[1<<j]-1\n",
    "                cnt[1<<j]=0\n",
    "            carry = temp[i] // 2\n",
    "            temp[i + 1] += carry\n",
    "            i+=1\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], target: int) -> int:\n",
    "        if sum(nums) < target:\n",
    "            return -1\n",
    "        cnt = Counter(nums)\n",
    "\n",
    "        ans = s = i = 0\n",
    "        while 1 << i <= target:\n",
    "            s += cnt[1 << i] * (1 << i)\n",
    "            mask = (1 << (i + 1)) - 1\n",
    "            i += 1\n",
    "            if s >= mask & target:\n",
    "                continue\n",
    "            ans += 1\n",
    "            while cnt[1 << i] == 0:\n",
    "                i += 1\n",
    "                ans += 1\n",
    "        return ans\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], target: int) -> int:\n",
    "\n",
    "        if sum(nums) < target: return -1\n",
    "        cnt = Counter(nums)\n",
    "        ans = s = i = 0\n",
    "\n",
    "        while 1 << i <= target:\n",
    "\n",
    "            s += cnt[1 << i] << i\n",
    "            mask = (1 << (i + 1)) - 1\n",
    "            i += 1\n",
    "            if s >= target & mask:\n",
    "                continue\n",
    "            ans += 1\n",
    "            while cnt[1 << i] == 0:\n",
    "                i += 1\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], target: int) -> int:\n",
    "        \n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        cnt = collections.defaultdict(int)\n",
    "\n",
    "        for i in range(32):\n",
    "            for j in range(n):\n",
    "                if (nums[j]>>i)&1:\n",
    "                    cnt[i]+=1\n",
    "        print(cnt)\n",
    "        print(bin(target)[2:])\n",
    "        res = 0\n",
    "        for i in range(32):\n",
    "            if (target>>i)&1==1:\n",
    "                print(cnt)\n",
    "                if cnt[i]>0:cnt[i]-=1\n",
    "                else:\n",
    "                    for k in range(1,i+1):\n",
    "                        cnt[k]+=cnt[k-1]//2\n",
    "                        cnt[k-1]%=2\n",
    "                    if cnt[i]>0: cnt[i]-=1\n",
    "                    else:\n",
    "                        flag = 0\n",
    "                        for j in range(i+1,32):\n",
    "                            if cnt[j]>0:\n",
    "                                flag = 1\n",
    "                                res+=j-i\n",
    "                                for k in range(j,i,-1):\n",
    "                                    cnt[k]-=1\n",
    "                                    cnt[k-1]+=2\n",
    "                                break\n",
    "                        print(res)\n",
    "                        if not flag: return -1\n",
    "                        cnt[i]-=1\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], target: int) -> int:\\\n",
    "        # 贪心\n",
    "        if sum(nums) < target: return -1\n",
    "        cnt = Counter(nums)  # 分桶\n",
    "        ans = s = i = 0  # ans拆分次数 s i左移位数/循环控制变量\n",
    "        while 1 << i <= target:\n",
    "            s += cnt[1 << i] << i  # ???前缀和?\n",
    "            mask = (1 << (i + 1)) - 1  # 1 11 111 ...\n",
    "            i += 1\n",
    "            if s >= target & mask:\n",
    "                continue\n",
    "            ans += 1  # 一定要找更大的数操作\n",
    "            while cnt[1 << i] == 0:\n",
    "                ans += 1  # 还没找到，继续找更大的数\n",
    "                i += 1\n",
    "        return ans\n",
    "\n",
    "        # SELF 排序 贪心 前缀和 位运算\n",
    "        nums = sorted(nums)\n",
    "        print(nums, target)\n",
    "        pre, n2 = 0, []\n",
    "        for i in nums:\n",
    "            if i & target:\n",
    "                target -= i\n",
    "                print(11, i, target, pre)\n",
    "            elif (pre + i) & target:\n",
    "                target -= (pre + i) & target\n",
    "                pre = pre + i - (pre + i) & target\n",
    "                print(22, i, target, pre)\n",
    "            else:\n",
    "                pre += i\n",
    "                print(33, i, target, pre)\n",
    "            \n",
    "\"\"\"\n",
    "        \n",
    "        for i in range(31):\n",
    "            mask = 1 << i\n",
    "            if target & mask and mask in nums:\n",
    "                target -= mask  # 删除已有位\n",
    "                nums.remove(mask)  # 删除已用元素\n",
    "        print(nums, target)\n",
    "        pre = [0]\n",
    "        for i in nums:\n",
    "            pre.append(pre[-1]+i) # 前缀和\n",
    "        print(pre, target)\n",
    "        \n",
    "        if pre[-1] < target: return -1\n",
    "        for n in nums:\n",
    "            if n > target:  # \n",
    "                k = n\n",
    "                break\n",
    "\n",
    "        for i in range(31, -1, -1):\n",
    "            mask = 1 << i\n",
    "            if k & mask:\n",
    "                mx = k\n",
    "                break\n",
    "        for i in range(31):\n",
    "            if target & \n",
    "\"\"\"\n",
    "        \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], target: int) -> int:\n",
    "        cnt = [0] * 32\n",
    "        for x in nums:\n",
    "            i = int(math.log2(x & -x))\n",
    "            cnt[i] += 1\n",
    "        \n",
    "        ans = 0\n",
    "        \n",
    "        mark = -1\n",
    "        for i in range(32):\n",
    "            if target >> i & 1:\n",
    "                if cnt[i] > 0:\n",
    "                    cnt[i] -= 1\n",
    "                elif mark < 0:\n",
    "                    mark = i\n",
    "            if cnt[i] > 0:\n",
    "                if mark > -1:\n",
    "                    ans += i - mark\n",
    "                    mark = -1\n",
    "                    cnt[i] -= 1\n",
    "                if i < 31:\n",
    "                    cnt[i+1] += cnt[i] >> 1\n",
    "        if mark >= 0:\n",
    "            return -1\n",
    "        else:\n",
    "            return ans\n",
    "                \n",
    "                    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], target: int) -> int:\n",
    "        ones = [0] * 32\n",
    "        for i in range(30, -1, -1):\n",
    "            if target >= pow(2, i):\n",
    "                ones[i] += 1\n",
    "                target -= pow(2, i)\n",
    "        d = {}\n",
    "        currVal = 1\n",
    "        for i in range(32):\n",
    "            d[currVal] = i\n",
    "            currVal *= 2\n",
    "        e = [0] * 32\n",
    "        for num in nums:\n",
    "            e[d[num]] += 1\n",
    "        # print(ones, e)\n",
    "        res = 0\n",
    "        for i in range(32):\n",
    "            if ones[i] == 1:\n",
    "                val = pow(2, i)\n",
    "                f = e.copy()\n",
    "                for j in range(i, -1, -1):\n",
    "                    if val > pow(2, j) * f[j]:\n",
    "                        val -= pow(2, j) * f[j]\n",
    "                        f[j] = 0\n",
    "                    else:\n",
    "                        f[j] -= val // pow(2, j)\n",
    "                        val = 0\n",
    "                        break\n",
    "                if val == 0:\n",
    "                    e = f\n",
    "                    # print(i, e, f)\n",
    "                else:\n",
    "                    for j in range(i + 1, 32):\n",
    "                        if e[j] >= 1:\n",
    "                            e[j] -= 1\n",
    "                            for k in range(i, j):\n",
    "                                e[k] += 1\n",
    "                                res += 1\n",
    "                            val = 0\n",
    "                            break\n",
    "                    if val > 0:\n",
    "                        return -1\n",
    "        return res\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], target: int) -> int:\n",
    "        if sum(nums) < target:\n",
    "            return -1\n",
    "        cnt = Counter(nums)\n",
    "        ans = s = i = 0\n",
    "        while 1 << i <= target:\n",
    "            s += cnt[1 << i] << i\n",
    "            mask = (1 << (i + 1)) - 1\n",
    "            i += 1\n",
    "            if s >= target & mask:\n",
    "                continue\n",
    "            ans += 1  # 一定要找更大的数操作\n",
    "            while cnt[1 << i] == 0:\n",
    "                ans += 1  # 还没找到，继续找更大的数\n",
    "                i += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], target: int) -> int:\n",
    "        if sum(nums)<target:return -1\n",
    "        ans=0\n",
    "        cnt=Counter(nums)\n",
    "        hero=1\n",
    "        while hero<=target:\n",
    "            if hero&target:\n",
    "                if cnt[hero]<=0:\n",
    "                    boss=hero\n",
    "                    while cnt[boss]==0:\n",
    "                        boss<<=1\n",
    "                    cnt[boss]-=1\n",
    "                    while boss>hero:\n",
    "                        boss>>=1\n",
    "                        cnt[boss]=1\n",
    "                        ans+=1\n",
    "                    cnt[hero]=2\n",
    "                cnt[hero]-=1\n",
    "            cnt[hero<<1] += cnt[hero]>>1\n",
    "            cnt[hero] &=1\n",
    "            hero<<=1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], target: int) -> int:\n",
    "        if sum(nums) < target: return -1\n",
    "        cnt = Counter(nums)\n",
    "        ans = 0\n",
    "        # smaller_numbers 记录所有更小的次幂的数的和\n",
    "        smaller_numbers = 0\n",
    "        for i in range(31):\n",
    "            # 先加上当前次幂的数值\n",
    "            smaller_numbers += cnt[1 << i] << i\n",
    "            if target >> i & 1:\n",
    "                # 如果更小的数之和是大于当前要表示的比特位，那么不需要进行操作\n",
    "                if smaller_numbers >= 1 << i:\n",
    "                    smaller_numbers -= 1 << i\n",
    "                else:\n",
    "                    # 否则寻找最小的更大的 2 的次幂\n",
    "                    for j in range(i + 1, 31):\n",
    "                        if cnt[1 << j]:\n",
    "                            cnt[1 << j] -= 1\n",
    "                            smaller_numbers += 1 << j\n",
    "                            smaller_numbers -= 1 << i\n",
    "                            ans += j - i\n",
    "                            break\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, A: List[int], T: int) -> int:\n",
    "        if sum(A) < T: return -1\n",
    "        cnt = Counter(x.bit_length() - 1 for x in A)\n",
    "        \n",
    "        res = 0\n",
    "        for x in range(T.bit_length()):\n",
    "            if T & 1 << x:\n",
    "                b = next(b for b in range(x, 32) if cnt[b])\n",
    "                res += b - x\n",
    "                cnt[b] -= 1\n",
    "                for i in range(x, b):\n",
    "                    cnt[i] += 1\n",
    "            cnt[x + 1] += cnt[x] // 2                \n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], target: int) -> int:\n",
    "        if sum(nums) < target:\n",
    "            return -1\n",
    "        d = collections.defaultdict(int)\n",
    "        for n in range(31):\n",
    "            d[1 << n] = n\n",
    "        s = [0] * 31\n",
    "        for n in nums:\n",
    "            s[d[n]] += 1\n",
    "        for i in range(31):\n",
    "            if target & (1 << i):\n",
    "                s[i] -= 1\n",
    "        f = 0\n",
    "        print(s)\n",
    "        for i in range(30):\n",
    "            if s[i] < 0:\n",
    "                f = 1\n",
    "            if s[i] >= 1:\n",
    "                if f:\n",
    "                    s[i + 1] += (s[i] - 1) // 2\n",
    "                    f = 0\n",
    "                else:\n",
    "                    s[i+1] += s[i] // 2\n",
    "                s[i] = 1     \n",
    "        pre = 30\n",
    "        ans = 0\n",
    "        for i in range(30, -1, -1):\n",
    "            if s[i] > 0:\n",
    "                pre = i\n",
    "            if s[i] < 0:\n",
    "                ans += (pre - i)\n",
    "                pre = i\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s: List[int], t: int) -> int:\n",
    "        if sum(s) < t:\n",
    "            return -1\n",
    "        f = [0] * 32\n",
    "        for v in s:\n",
    "            f[v.bit_length() - 1] += 1\n",
    "        ans = 0\n",
    "        for i in range(t.bit_length()):\n",
    "            if (t & (1 << i)) > 0:\n",
    "                if f[i] > 0:\n",
    "                    f[i] -= 1\n",
    "                else:\n",
    "                    k = i\n",
    "                    while f[k] == 0:\n",
    "                        f[k] = 1\n",
    "                        k += 1\n",
    "                        ans += 1\n",
    "                    f[k] -= 1\n",
    "            f[i + 1] += f[i] // 2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], target: int) -> int:\n",
    "        if sum(nums) < target:\n",
    "            return -1\n",
    "        cnt = Counter(nums)\n",
    "        arr = []\n",
    "        while target > 0:\n",
    "            arr.append(target & 1)\n",
    "            target >>= 1\n",
    "        ret = 0\n",
    "        pre_sum = 0\n",
    "        for i, bit in enumerate(arr):\n",
    "            num = 2 ** i\n",
    "            pre_sum += cnt[num] * num\n",
    "            if bit == 1:\n",
    "                if pre_sum >= num:\n",
    "                    pre_sum -= num\n",
    "                else:\n",
    "                    j = i + 1\n",
    "                    while j < 31:\n",
    "                        a = 2 ** j\n",
    "                        if cnt[a] > 0:\n",
    "                            cnt[a] -= 1\n",
    "                            ret += j - i\n",
    "                            pre_sum += num\n",
    "                            for k in range(i, j):\n",
    "                                cnt[2 ** k] += 1\n",
    "                            break\n",
    "                        j += 1\n",
    "                    if j == 31:\n",
    "                        return -1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        if sum(nums) < target:\n",
    "            return - 1\n",
    "        nums.sort(reverse = True)\n",
    "        res = 0\n",
    "        for i in range(32):\n",
    "            s = 0\n",
    "            if target & (1 << i):\n",
    "                x = 1 << i \n",
    "                while nums and nums[-1] < x and s < x:\n",
    "                    s += nums.pop()\n",
    "                if s >= x:\n",
    "                    s -= x \n",
    "                elif nums[-1] == x:\n",
    "                    nums.pop()\n",
    "                else:\n",
    "                    last = nums.pop()\n",
    "                    while last > x:\n",
    "                        last //= 2 \n",
    "                        nums.append(last)\n",
    "                        res += 1 \n",
    "        return res \n",
    "\n",
    "      \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], target: int) -> int:\n",
    "        if sum(nums) < target:\n",
    "            return -1\n",
    "        cnt = Counter(nums)\n",
    "        ans = s = i = 0\n",
    "        while 1 << i <= target:\n",
    "            s += cnt[1 << i] << i\n",
    "            mask = (1 << (i + 1)) - 1\n",
    "            i += 1\n",
    "            if s >= target & mask:\n",
    "                continue\n",
    "            ans += 1  # 一定要找更大的数操作\n",
    "            while cnt[1 << i] == 0:\n",
    "                ans += 1  # 还没找到，继续找更大的数\n",
    "                i += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], target: int) -> int:\n",
    "        nums.sort()\n",
    "        # presum = [0]\n",
    "        # for num in nums:\n",
    "        #     presum.append(presum[-1] + num)\n",
    "        sum = 0\n",
    "        j = 0\n",
    "        n = len(nums)\n",
    "        mask = 0\n",
    "        ans = 0\n",
    "        for i in range(32):\n",
    "            mask += (1 << i)\n",
    "            while j < n and nums[j] <= mask:\n",
    "                sum += nums[j]\n",
    "                j += 1\n",
    "            if target & (1 << i):\n",
    "                if sum < (target & mask):\n",
    "                    # print(i)\n",
    "                    if j == n:\n",
    "                        return -1\n",
    "                    else:\n",
    "                        sum += nums[j]\n",
    "                        ans += (nums[j].bit_length() - (i + 1))\n",
    "                        j += 1\n",
    "                        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], target: int) -> int:\n",
    "        if sum(nums) < target:\n",
    "            return -1\n",
    "        c = Counter(nums)\n",
    "        cnt = 0 \n",
    "        acc = 0\n",
    "        for i in range(40):\n",
    "            acc += c[1<<i] *(1<<i)\n",
    "            if target&(1<<i):\n",
    "                #print(i,acc)\n",
    "                if acc < (1<<i):\n",
    "                    j = i+1\n",
    "                    while j <40:\n",
    "                        if c[1<<j]>0:\n",
    "                            cnt += j-i\n",
    "                            c[1<<j] -=1\n",
    "                            acc +=(1<<j) - (1<<i)\n",
    "                            #print(cnt,j,i,acc)\n",
    "                            break\n",
    "                        j +=1\n",
    "                else:\n",
    "                    acc -=(1<<i)\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], target: int) -> int:\n",
    "        if sum(nums) < target:return -1\n",
    "        cnts = Counter(nums)\n",
    "        i = 0\n",
    "        s = 0\n",
    "        ans = 0\n",
    "        while s < target:\n",
    "            s += cnts[1 << i] * (1 << i)\n",
    "            mask = 2 ** (i + 1) - 1\n",
    "            i += 1\n",
    "            if s >= mask & target:\n",
    "                continue\n",
    "            ans += 1\n",
    "            while cnts[1 << i] == 0:\n",
    "                i += 1\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], target: int) -> int:\n",
    "        if sum(nums) < target:\n",
    "            return -1\n",
    "        cnt = Counter(nums)\n",
    "        ans = s = i = 0\n",
    "        while 1 << i <= target:\n",
    "            s += cnt[1 << i] << i\n",
    "            mask = (1 << (i + 1)) - 1\n",
    "            i += 1\n",
    "            if s >= target & mask:\n",
    "                continue\n",
    "            ans += 1  # 一定要找更大的数操作\n",
    "            while cnt[1 << i] == 0:\n",
    "                ans += 1  # 还没找到，继续找更大的数\n",
    "                i += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def find_up(self, now):\n",
    "        if now not in self.dic:\n",
    "            return -1\n",
    "        if self.dic[now] <= 0:\n",
    "            self.dic[now] = self.dic[now] + 2\n",
    "            nex = self.find_up(now*2)\n",
    "            if nex == -1:\n",
    "                return -1\n",
    "            self.dic[now * 2] = self.dic[now * 2] - 1\n",
    "            return 1 + nex\n",
    "        else:\n",
    "            return 0\n",
    "    def minOperations(self, nums: List[int], target: int) -> int:\n",
    "        \n",
    "        if sum(nums) < target:\n",
    "            return -1\n",
    "        \n",
    "        self.dic = {}\n",
    "        for i in range(35):\n",
    "            self.dic.update({2 ** i: 0})\n",
    "        for num in nums:\n",
    "            self.dic[num] = self.dic[num] + 1\n",
    "        now = 1\n",
    "        ans = 0\n",
    "        check = []\n",
    "        while(target > 0 and now <= target):\n",
    "            if target % (now*2) != 0:\n",
    "                if self.dic[now] == 0:\n",
    "                    tmp = self.find_up(now)\n",
    "                    if tmp == -1:\n",
    "                        return -1\n",
    "                    ans = ans + tmp\n",
    "                    check.append([now,tmp])\n",
    "                \n",
    "                self.dic[now] = self.dic[now] - 1\n",
    "                target = target - now\n",
    "            self.dic[now * 2] = self.dic[now * 2] + self.dic[now] // 2\n",
    "            now = now * 2\n",
    "        # return check\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], target: int) -> int:\n",
    "        if sum(nums) < target:\n",
    "            return -1\n",
    "        cnt = Counter(nums)\n",
    "        ans = s = i = 0\n",
    "        while 1 << i <= target:\n",
    "            s += cnt[1 << i] << i\n",
    "            mask = (1 << (i + 1)) - 1\n",
    "            i += 1\n",
    "            if s >= target & mask:\n",
    "                continue\n",
    "            ans += 1\n",
    "            while cnt[1 << i] == 0:\n",
    "                ans += 1\n",
    "                i += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, a: List[int], t: int) -> int:\n",
    "        a.sort(reverse=True)\n",
    "        if sum(a)<t:\n",
    "            return -1\n",
    "        s = sum(a)\n",
    "        ans = 0\n",
    "        pre = 0\n",
    "        b = bin(t)[2:][::-1]\n",
    "        def f(x):\n",
    "            if x==0:\n",
    "                return 0\n",
    "            if x==1:\n",
    "                return 1 \n",
    "            for j in range(100):\n",
    "                if (1<<j)>x:\n",
    "                    return (1<<(j-1))\n",
    "        for j in range(len(b)):\n",
    "            k = (1<<j)\n",
    "            while a and (a[-1]<=k):\n",
    "                tmp = a.pop()\n",
    "                pre += tmp\n",
    "            if b[j]=='0':\n",
    "                pass \n",
    "            else:\n",
    "                if pre>=k:\n",
    "                    pre-=k \n",
    "                else:\n",
    "                    need = k  \n",
    "                    tmp = a.pop()\n",
    "                    while tmp!=need:\n",
    "                        tmp = tmp//2 \n",
    "                        a.append(tmp)\n",
    "                        ans+=1\n",
    "        return ans \n",
    "\n",
    "            \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "\n",
    "class Solution:\n",
    "    def to_binary_index(self, resi):\n",
    "        bina = \"{0:b}\".format(resi)\n",
    "        bina_list = []\n",
    "        for i in range(len(bina)):\n",
    "            if bina[i] == '1':\n",
    "                bina_list.append(len(bina) - i - 1)\n",
    "        return bina_list\n",
    "\n",
    "    def minOperations(self, nums: List[int], target: int) -> int:\n",
    "        n = sum(nums)\n",
    "        if target > n:\n",
    "            return -1\n",
    "        elif target == n:\n",
    "            return 0\n",
    "        nums.sort(reverse=True)\n",
    "        bina = \"{0:b}\".format(target)\n",
    "        print(bina)\n",
    "        tmp = 0\n",
    "        ans = 0\n",
    "        for i in range(len(bina) - 1, -1, -1):\n",
    "            if bina[i] != '1':\n",
    "                continue\n",
    "            now = math.pow(2, len(bina) - i - 1)\n",
    "            while len(nums) > 0 and now > nums[-1]:\n",
    "                tmp += nums.pop()\n",
    "            # print(now, tmp, nums)\n",
    "            if tmp >= now:\n",
    "                tmp -= now\n",
    "            elif nums[-1] == now:\n",
    "                nums.pop()\n",
    "            else:\n",
    "                x = nums.pop()\n",
    "                while x > now:\n",
    "                    x = x // 2\n",
    "                    nums.append(x)\n",
    "                    ans += 1\n",
    "            # print(now, nums, ans)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "        return cnt\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "                \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], target: int) -> int:\n",
    "        if sum(nums) < target:\n",
    "            return -1\n",
    "        cnt = Counter(nums)\n",
    "        ans = s = i = 0\n",
    "        while 1 << i <= target:\n",
    "            s += cnt[1 << i] << i\n",
    "            mask = (1 << (i + 1)) - 1\n",
    "            i += 1\n",
    "            if s >= target & mask:\n",
    "                continue\n",
    "            ans += 1  # 一定要找更大的数操作\n",
    "            while cnt[1 << i] == 0:\n",
    "                ans += 1  # 还没找到，继续找更大的数\n",
    "                i += 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], target: int) -> int:\n",
    "        if sum(nums) < target:\n",
    "            return -1\n",
    "        cnt = Counter(nums)\n",
    "        ans = s = 0\n",
    "        for i in range(31):\n",
    "            s += cnt[1 << i] << i\n",
    "            if target >> i & 1:\n",
    "                if s >= 1 << i:\n",
    "                    s -= 1 << i\n",
    "                else:\n",
    "                    for j in range(i + 1, 31):\n",
    "                        if cnt[1 << j]:\n",
    "                            cnt[1 << j] -= 1\n",
    "                            s += (1 << j) - (1 << i)\n",
    "                            ans += j - i\n",
    "                            break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], target: int) -> int:\n",
    "        if sum(nums) < target:\n",
    "            return -1\n",
    "        count_dict = Counter(nums)\n",
    "        lst = [count_dict[1 << i] for i in range(31)]\n",
    "        target_lst = list(map(int, list(bin(target)[2:][::-1])))\n",
    "        target_lst.extend((31 - len(target_lst)) * [0])\n",
    "        count = 0\n",
    "        for i in range(31):\n",
    "            for j in range(i):\n",
    "                q, r = divmod(lst[j], 2)\n",
    "                lst[j] = r\n",
    "                lst[j + 1] += q\n",
    "            if target_lst[i] <= lst[i]:\n",
    "                lst[i] -= target_lst[i]\n",
    "            else:\n",
    "                for j in range(i + 1, 31):\n",
    "                    if lst[j] > 0:\n",
    "                        lst[j] -= 1\n",
    "                        count += j - i\n",
    "                        for k in range(i, j):\n",
    "                            lst[k] = 1\n",
    "                        break\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], target: int) -> int:\n",
    "        s = sum(nums)\n",
    "        if s < target:\n",
    "            return -1\n",
    "        v = []\n",
    "        k = 0\n",
    "        while target > 0:\n",
    "            if target & 1:\n",
    "                v.append(k)\n",
    "            k += 1\n",
    "            target >>= 1\n",
    "        nums.sort()\n",
    "        print(v, nums)\n",
    "        vidx = 0\n",
    "        cnt = Counter()\n",
    "        step = 0\n",
    "        for i in nums:\n",
    "            now = i\n",
    "            cnt[now] += 1\n",
    "            while cnt[now] == 2:\n",
    "                cnt[now] -= 2\n",
    "                now <<= 1\n",
    "                cnt[now] += 1\n",
    "            if vidx == len(v):\n",
    "                return step\n",
    "            key = 1 << v[vidx]\n",
    "            while now > key:\n",
    "                step += 1\n",
    "                cnt[now] -= 1\n",
    "                now >>= 1\n",
    "                cnt[now] += 2\n",
    "            while vidx < len(v) and cnt[key] > 0:\n",
    "                vidx += 1\n",
    "                cnt[key] -= 1\n",
    "                if vidx < len(v):\n",
    "                    key = 1 << v[vidx]\n",
    "        return step"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], target: int) -> int:\n",
    "        nums_sum = 0\n",
    "        nums_cnt = [0] * 32\n",
    "        for n in nums:\n",
    "            bits = n.bit_length()\n",
    "            nums_cnt[bits - 1] += 1\n",
    "            nums_sum += n\n",
    "\n",
    "        if nums_sum < target:\n",
    "            return -1\n",
    "\n",
    "        while target:\n",
    "            bits = target.bit_length()\n",
    "            p = bits - 1\n",
    "            nums_cnt[p] -= 1\n",
    "            target -= 1 << p\n",
    "\n",
    "        def get_last_neg():\n",
    "            j = 31\n",
    "            while 0 <= j and nums_cnt[j] >= 0:\n",
    "                j -= 1\n",
    "            return j\n",
    "\n",
    "        def get_first_neg():\n",
    "            j = 0\n",
    "            while j < 32 and nums_cnt[j] >= 0:\n",
    "                j += 1\n",
    "            return j\n",
    "\n",
    "        def get_first_pos(start):\n",
    "            while start < 32 and nums_cnt[start] <= 0:\n",
    "                start += 1\n",
    "            return start\n",
    "\n",
    "        ret = 0\n",
    "        j = get_first_neg()\n",
    "        while j < 32:\n",
    "            s = sum([(1 << i) * v for i, v in enumerate(nums_cnt[:j]) if v > 0])\n",
    "            can_be_merged = (1 << j) <= s\n",
    "\n",
    "            pos = get_first_pos(j + 1)\n",
    "            if can_be_merged:\n",
    "                nums_cnt[j] += 1\n",
    "                nums_cnt[j - 1] -= 2\n",
    "            else:\n",
    "                pos = get_first_pos(j + 1)\n",
    "                if pos == 32:\n",
    "                    nums_cnt[j] += 1\n",
    "                    nums_cnt[j - 1] -= 2\n",
    "                else:\n",
    "                    nums_cnt[pos] -= 1\n",
    "                    nums_cnt[pos - 1] += 2\n",
    "                    ret += 1\n",
    "            j = get_first_neg()\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], target: int) -> int:\n",
    "        total = sum(nums)\n",
    "        if total < target:\n",
    "            return -1\n",
    "        nums = [-x for x in nums]\n",
    "        heapq.heapify(nums)\n",
    "        cnt = 0\n",
    "        # while len(nums) > 0:\n",
    "        #     print (heapq.heappop(nums))\n",
    "\n",
    "        while target > 0:\n",
    "            top = -heapq.heappop(nums)\n",
    "            # print (top)\n",
    "            if total - top >= target:\n",
    "                total -= top\n",
    "            elif top > target:\n",
    "                cnt += 1\n",
    "                heapq.heappush(nums, -(top >> 1))        \n",
    "                heapq.heappush(nums, -(top >> 1))\n",
    "            else:\n",
    "                target -= top\n",
    "                total -= top\n",
    "        \n",
    "        return cnt\n",
    "            \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    1. 什么情况下结果不存在\n",
    "    sum(nums) < target时结果不存在;\n",
    "    如果sum(nums) >= target,那么最糟糕的情况是全部拆分为1，也是可以有解的\n",
    "\n",
    "    2.通过二进制的方式思考(2的幂)\n",
    "\n",
    "    3.从低位到高位思考\n",
    "    要求的是最小的操作次数，那么最好的情况就是可以使用现有的数组元素构造出target目标元素，退而求其次就是需要使用 \n",
    "    数组元素构造出target中的一部分，也就是需要从低到高进行构建\n",
    "\n",
    "    数组中的所有小于等于2^i的元素和>=2^i,能否不操作构造出2^i\n",
    "    1.可以的，通过数学归纳法可以证明\n",
    "        2^0=1 -> s>=1,那么必然是有1的，可以直接构造得出\n",
    "        2^1=2 -> s>=2,如果有2，直接可以构造，如果没有2，那么至少有两个1，可以构造\n",
    "        2^2=4 -> s>=4,如果有4，直接可以构造，如果没有4，那么数组中的元素都是<=2的，通过第二点可知，可以构造出一\n",
    "        个2，同时由于s>=4,那么剩余的结果>=2,根据2还是可以构造出一个，最后构造出4\n",
    "        ……\n",
    "        2^k   -> s >= 2^k可以构造出\n",
    "        2^k+1 -> 2 >= 2^k+1,如果有2^k+1,那么可以直接构造出结果,如果不存在，那么数组中的元素都是<=2^k的，通过上\n",
    "        一点可知可以构造出一个2^k，在构造出一个2^k后，剩余的结果是>=2^k的，还可以构造出一个2^k,最后构造出结果\n",
    "    2. 算法过程\n",
    "        遍历target的每一个二进制位，1则尝试构造，0则不用考虑\n",
    "        1. 计算s,如果s >= 2^i,可以直接构造,从s中减去2^i\n",
    "        2. 如果s<2^i,需要从比2^i大的数2^j中进行拆分\n",
    "            拆分可以得到2^j-1,2^j-2.....2^i+1,2^i,2^i\n",
    "            可以看到：\n",
    "            1.操作次数为j - i\n",
    "            2.不仅得到i,还有j-1,j-2,....,i+1,也就是下一位可以从j开始\n",
    "            3.这里想不明白的因为涉及到s的加减，可以直接构造的话要减去，不可以直接构造的话得拆分，拆分后s应当如何 \n",
    "            计算如果从j开始的话(参考了灵神的写法好简洁)\n",
    "            4.所以还是朴素写法吧，不要直接跳，有点想不明白怎么写       \n",
    "    '''\n",
    "    def minOperations(self, nums: List[int], target: int) -> int:\n",
    "        \n",
    "        if(sum(nums) < target):\n",
    "            return -1\n",
    "\n",
    "        cnt = Counter(nums)\n",
    "        ans = s = i = 0\n",
    "        flag = 0\n",
    "        while((1 << i) <= target):\n",
    "            \n",
    "            s += cnt[1<<i] * (1 << i)\n",
    "\n",
    "            if((target>>i) & 1):\n",
    "                print(str(1<<i) + \" \" + str(s))\n",
    "                if(s >= (1<<i)):\n",
    "                    s -= (1<<i)\n",
    "                    i += 1\n",
    "                    continue\n",
    "                \n",
    "                #查找比1<<i大的数\n",
    "                j = i + 1\n",
    "                while(cnt[1<<j] == 0):\n",
    "                    j += 1\n",
    "                \n",
    "                ans += j - i\n",
    "                for k in range(i,j):\n",
    "                    cnt[1<<k] += 1\n",
    "                cnt[1<<j] -= 1\n",
    "                s += 1 <<i\n",
    "                i += 1\n",
    "                \n",
    "            else:\n",
    "                i += 1\n",
    "\n",
    "        return ans\n",
    "\n",
    "                \n",
    "\n",
    "                \n",
    "\n",
    "                \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], target: int) -> int:\n",
    "        if sum(nums) < target: return -1\n",
    "\n",
    "\n",
    "        from collections import defaultdict\n",
    "        dct = defaultdict(int)\n",
    "        for n in nums:\n",
    "            dct[int(math.log(n, 2))] += 1\n",
    "\n",
    "        print(dct)\n",
    "\n",
    "        res, i = 0, 0\n",
    "        while target:\n",
    "            if target & 1:\n",
    "                print(i, '-------')\n",
    "                if dct[i] > 0:\n",
    "                    dct[i] -= 1\n",
    "                else:\n",
    "                    getted = False\n",
    "                    for j in range(i + 1, 33):\n",
    "                        \n",
    "                        if dct[j] > 0:\n",
    "                            print(j,'====', dct[j])\n",
    "                            dct[j] -= 1\n",
    "                            for idx in range(j - 1, i - 1, -1):\n",
    "                                dct[idx] += 1\n",
    "                            res += j - i\n",
    "                            getted = True\n",
    "                            break\n",
    "                    if not getted:\n",
    "                        return -1\n",
    "\n",
    "            dct[i + 1] += dct[i] // 2\n",
    "\n",
    "            print(i, [{k: dct[k]} for k in sorted(dct.keys())])\n",
    "\n",
    "            i += 1\n",
    "            target >>= 1\n",
    "\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], target: int) -> int:\n",
    "        # 先判断 nums 总数是否大于 target\n",
    "        if sum(nums) < target:\n",
    "            return -1\n",
    "\n",
    "        u = [0] * 31\n",
    "        r = 0\n",
    "\n",
    "        for v in nums:\n",
    "            u[int(math.log2(v))] += 1\n",
    "\n",
    "        def f(i, p=False, n=1):\n",
    "            nonlocal r\n",
    "\n",
    "            if p:\n",
    "                if u[i] > 0:\n",
    "                    u[i] -= 1\n",
    "                else:\n",
    "                    f(i + 1, True)\n",
    "                    u[i] += 1\n",
    "                    r += 1\n",
    "            else:\n",
    "                if u[i] >= n:\n",
    "                    u[i] -= n\n",
    "                    return True\n",
    "                elif i == 0 or f(i - 1, False, (n - u[i]) * 2) == False:\n",
    "                    return False\n",
    "                else:\n",
    "                    u[i] = 0\n",
    "                    return True\n",
    "\n",
    "        for i in range(31):\n",
    "            if target & (2**i):\n",
    "                if f(i):\n",
    "                    pass\n",
    "                else:\n",
    "                    f(i, True)\n",
    "                    u[i] -= 1\n",
    "\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], target: int) -> int:\n",
    "        if sum(nums) < target:\n",
    "            return -1\n",
    "        nums.sort()\n",
    "        # c = 2**31\n",
    "        # arr = deque()\n",
    "        # while target > 0:\n",
    "        #     if c > target:\n",
    "        #         c //= 2\n",
    "        #     else:\n",
    "        #         target -= c\n",
    "        #         arr.appendleft(c)\n",
    "        #         c //= 2\n",
    "        # print(arr)\n",
    "        \n",
    "        s = sum(nums)\n",
    "        arr = SortedList(nums)\n",
    "        ans = 0\n",
    "        while target > 0 and arr:\n",
    "            if arr[-1] <= target:\n",
    "                target -= arr[-1]\n",
    "                s -= arr[-1]\n",
    "                arr.pop()\n",
    "            else:\n",
    "                if s - arr[-1] >= target:\n",
    "                    s -= arr[-1]\n",
    "                    arr.pop()\n",
    "                else:\n",
    "                    temp = arr.pop()\n",
    "                    ans += 1\n",
    "                    arr.add(temp//2)\n",
    "                    arr.add(temp//2)\n",
    "            # print(arr)\n",
    "        return ans\n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "                \n",
    "                "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
